﻿#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;//数组
	int size;//实际上堆的大小
	int capacity;//堆的最大容量
}HP;

void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);//使用前提是左右子树是堆
void AdjustDown(int* a, int n, int parent);//使用前提是如果调整为大堆，那么左右子树应该是大堆，如果是小堆，那么左右子树应该是小堆

void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
// 
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);



//任意数组都可以看成完全二叉树，但是不一定是堆

//堆只规定树的任何一个父亲与孩子的大小关系，并未规定兄弟结点的大小关系
//因此小堆（任何一个父亲都小于或等于孩子）不一定是升序，大堆（任何一个父亲都大于或等于孩子）不一定是降序
//堆在物理结构（实际的存储结构）上是数组，在逻辑结构（为了方便理解想象出来的）上是二叉树


//堆的应用：堆排序，topk问题(就是找最大/小的前k个)，优先级队列

